package com.zhangx.datastructure.graph;

/**
 * @ClassName MiniSpanTree
 * @Description 最小生成树
 * P245
 * @Author zhangx
 * @Date 2021/1/15 8:29
 **/
public class MiniSpanTree {

    int INFINITY = 65536;//一般设置一个不可能的大的数

    int MAXVEX = 9;

    //    顶点
    Vertex[] vexs = new Vertex[MAXVEX];
    //    邻接矩阵
    int[][] arc = new int[MAXVEX][MAXVEX];

    /**
     * 查询时候看每个定点是否有访问过
     */
    boolean[] visited = new boolean[MAXVEX];

    int numVertexes;//顶点数
    int numEdges = 15;//边数

    Edge[] edges = new Edge[numEdges];

    /**
     * 顶点
     */
    class Vertex{

        private String data;

        public Vertex(String data){
            this.data = data;
        }

        @Override
        public String toString() {
            return "Vertex{" +
                    "data='" + data + '\'' +
                    '}';
        }
    }

    /**
     * 克鲁斯卡尔查找最小生成树时候用到的边集数组
     */
    public class Edge{
        int begin;
        int end;
        int weight;

        public Edge(int begin,int end,int weight){
            this.begin = begin;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "begin=" + begin +
                    ", end=" + end +
                    ", weight=" + weight +
                    '}';
        }
    }

    /**
     * 构建邻接矩阵
     */
    public void init(){
//        ---------------构建邻接矩阵----------------
//        9个点
        for (int i = 0; i < 9; i++) {
            vexs[i] = new Vertex("V"+i);
        }
        numVertexes = 9;
        numEdges = 14;
        int[] a0 = new int[]{0,10,INFINITY,INFINITY,INFINITY,11,INFINITY,INFINITY,INFINITY};
        int[] a1 = new int[]{10,0,18,INFINITY,INFINITY,INFINITY,16,INFINITY,12};
        int[] a2 = new int[]{INFINITY,INFINITY,0,22,INFINITY,INFINITY,INFINITY,INFINITY,8};
        int[] a3 = new int[]{INFINITY,INFINITY,22,0,20,INFINITY,INFINITY,16,21};
        int[] a4 = new int[]{INFINITY,INFINITY,INFINITY,20,0,26,INFINITY,7,INFINITY};
        int[] a5 = new int[]{11,INFINITY,INFINITY,INFINITY,26,0,17,INFINITY,INFINITY};
        int[] a6 = new int[]{INFINITY,16,INFINITY,INFINITY,INFINITY,17,0,19,INFINITY};
        int[] a7 = new int[]{INFINITY,INFINITY,INFINITY,16,7,INFINITY,19,0,INFINITY};
        int[] a8 = new int[]{INFINITY,12,8,21,INFINITY,INFINITY,INFINITY,INFINITY,0};

        arc[0] = a0;
        arc[1] = a1;
        arc[2] = a2;
        arc[3] = a3;
        arc[4] = a4;
        arc[5] = a5;
        arc[6] = a6;
        arc[7] = a7;
        arc[8] = a8;

        System.out.println("  V0 V1 V2 V3 V4 V5 V6 V7 V8");
        for (int i = 0; i < arc.length; i++) {
            String line = "v"+i;
            for (int j = 0; j < arc[i].length; j++) {
                line = line + " " + arc[i][j];
            }
            System.out.println(line);
        }

//        --------------构建边集数组---------------

        edges[0] = new Edge(4,7,7);
        edges[1] = new Edge(2,8,8);
        edges[2] = new Edge(0,1,10);
        edges[3] = new Edge(0,5,11);
        edges[4] = new Edge(1,8,12);
        edges[5] = new Edge(3,7,16);
        edges[6] = new Edge(1,6,16);
        edges[7] = new Edge(5,6,17);
        edges[8] = new Edge(1,2,18);
        edges[9] = new Edge(6,7,19);
        edges[10] = new Edge(3,4,20);
        edges[11] = new Edge(3,8,21);
        edges[12] = new Edge(2,3,22);
        edges[13] = new Edge(3,6,24);
        edges[14] = new Edge(4,5,26);
    }


    /**
     * 普里姆算法最小生成树
     * 看P250 7-6-6清晰
     * 简单说 就是先找一个起始节点，再找起始节点的临界点权重最小的，连起来，记录当前已经包含2个节点了
     * 再从这两个节点找邻接点（排除2个自身），找到最小权重的连起来，将第三个纳入已包含
     * 再从这三个节点找邻接点（排除3个自身），找到最小权重的连起来，将第四个纳入已包含
     * 不断重复直到所有节点纳入进来，这样连线关系就确定了
     *
     * 适用于稠密图u，变多
     * O(n^2)
     */
    void prim(){
        int min,j,k = 0;
        int[] adjvex = new int[MAXVEX];//顶点下标
        int[] lowcost = new int[MAXVEX];//相关顶点编的权值
        lowcost[0] = 0;//初始化V0权值，加入生成树；=0就是代表已加入生成树，index 代表第几个节点加入了生成树，最终应该是9个都进来
        adjvex[0] = 0;//第一个顶点下标为0
//        排除0节点，取其他
        for (int i = 1; i < numVertexes; i++) {//读取了邻接矩阵第一行数据，排除V0
            lowcost[i] = arc[0][i];//将v0顶点有边的权值放入数组
            adjvex[i] = 0;//初始化为v0下标
        }
//        --------------------------生成树--------------------------
        for (int i = 1; i < numVertexes; i++) {
            min = INFINITY;//最小权值-不可能
            j = 1;//顶点下标的变量
            k = 0;//最小权值的的顶点下标

            while (j<numVertexes){ //循环全部顶点
//               当权值！=0且不是min，就是一个存在的可行值
//                不断找到最小的min值
                if (lowcost[j]!=0 && lowcost[j]<min){
                    min = lowcost[j];//将其权作为最小
                    k = j;//保存下标
                }

                j++;
            }
//            打印的是当前顶点边中权值最小的边 顶点->目的地 下标  合计99
            System.out.println(adjvex[k]+"->"+k+"("+arc[adjvex[k]][k]+")");
            lowcost[k] = 0;//当前顶点权值为0，已经完成任务，下标k的顶点完成任务
            for (j = 1; j < numVertexes; j++) {//若下标为k的顶点各边权值<此前这些顶点未加入生成树的权值
                if (lowcost[j]!=0 && arc[k][j]<lowcost[j]){
                    lowcost[j] = arc[k][j];//较小的权值存入
                    adjvex[j] = k;//k顶点下标进入adjvex
                }
            }
        }
//        --------------------------生成树--------------------------

    }

    /**
     * 克鲁斯卡尔算法
     * 从最小的边入手，把没连接过的点连接起来
     * 适用于边少的稀疏图
     * O(eloge)
     */
    void kruscal(){

        int[] parent = new int[MAXVEX];//用于判断边与边是否形成环路
//        java这一步不需要 初始值就是0
        for (int i = 0; i < numVertexes; i++) {
            parent[i] = 0;
        }
//        循环每一条边,边都是根据weight排序了
        for (int i = 0; i < numEdges; i++) {
            int n = find(parent,edges[i].begin);
            int m = find(parent,edges[i].end);
            if (n!=m){//这证明此边没有与现在生成树形成环路
                parent[n] = m;//n起点，m 终点
                System.out.println(edges[i]);
            }
        }
    }

    /**
     * 克鲁斯卡尔find
     * @param parent
     * @param f
     * @return
     */
    int find(int[] parent,int f){
        while (parent[f]>0){
            f = parent[f];
        }
        return f;
    }


    public static void main(String[] args) {
        MiniSpanTree miniSpanTree = new MiniSpanTree();
        miniSpanTree.init();
//        miniSpanTree.prim();
        miniSpanTree.kruscal();
    }
}
